{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Common Supersequence "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestCommonSupersequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最短公共超序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串&nbsp;<code>str1</code> 和&nbsp;<code>str2</code>，返回同时以&nbsp;<code>str1</code>&nbsp;和&nbsp;<code>str2</code>&nbsp;作为 <strong>子序列</strong> 的最短字符串。如果答案不止一个，则可以返回满足条件的 <strong>任意一个</strong> 答案。</p>\n",
    "\n",
    "<p>如果从字符串 <code>t</code> 中删除一些字符（也可能不删除），可以得到字符串 <code>s</code> ，那么 <code>s</code> 就是 t 的一个子序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>str1 = \"abac\", str2 = \"cab\"\n",
    "<strong>输出：</strong>\"cabac\"\n",
    "<strong>解释：</strong>\n",
    "str1 = \"abac\" 是 \"cabac\" 的一个子串，因为我们可以删去 \"cabac\" 的第一个 \"c\"得到 \"abac\"。 \n",
    "str2 = \"cab\" 是 \"cabac\" 的一个子串，因为我们可以删去 \"cabac\" 末尾的 \"ac\" 得到 \"cab\"。\n",
    "最终我们给出的答案是满足上述属性的最短字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>str1 = \"aaaaaaaa\", str2 = \"aaaaaaaa\"\n",
    "<strong>输出：</strong>\"aaaaaaaa\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= str1.length, str2.length &lt;= 1000</code></li>\n",
    "\t<li><code>str1</code> 和&nbsp;<code>str2</code>&nbsp;都由小写英文字母组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-common-supersequence](https://leetcode.cn/problems/shortest-common-supersequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-common-supersequence](https://leetcode.cn/problems/shortest-common-supersequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abac\"\\n\"cab\"', '\"aaaaaaaa\"\\n\"aaaaaaaa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        L1,L2 = len(str1),len(str2)\n",
    "        dp_pre = { j:str2[j:] for j in range(L2)}\n",
    "        for i in range(L1)[::-1]:\n",
    "            dp = {}\n",
    "            for j in range(L2)[::-1]:\n",
    "                if str1[i]==str2[j]:\n",
    "                    if i+1==L1:\n",
    "                        dp[j] = str2[j:]\n",
    "                    elif j+1==L2:\n",
    "                        dp[j] = str1[i:]\n",
    "                    else:\n",
    "                        dp[j] = str1[i] + dp_pre[j+1]\n",
    "                else:\n",
    "                    right_state = dp_pre[j]\n",
    "                    down_state = str1[i:] if j+1== L2 else dp[j+1]\n",
    "                    if len(right_state) < len(down_state):\n",
    "                        dp[j] = str1[i] + right_state\n",
    "                    else:\n",
    "                        dp[j] = str2[j] + down_state\n",
    "            dp_pre =dp\n",
    "        return dp[0]\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m, n = len(str1), len(str2)\n",
    "        s = [\"\"] * (n+1)\n",
    "        # 查找公共子序列\n",
    "        for i in range(m):\n",
    "            st = \"\"\n",
    "            for j in range(1, n+1):\n",
    "                stt = s[j]\n",
    "                if str1[i] == str2[j-1]:\n",
    "                    s[j] = st + str1[i]\n",
    "                elif len(s[j-1]) > len(s[j]):\n",
    "                    s[j] = s[j-1]\n",
    "                st = stt\n",
    "        ans = \"\"\n",
    "        # 按照公共子序列切分对齐填入\n",
    "        for i in s[-1]:\n",
    "            x, str1 = str1.split(i, 1)\n",
    "            y, str2 = str2.split(i, 1)\n",
    "            ans += x+y+i \n",
    "        return ans + str1 + str2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class LcsLis:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    def longest_common_subsequence(self, s1, s2) -> int:\n",
    "        # 使用LIS的办法求LCS\n",
    "        if len(s1) > len(s2):\n",
    "            s1, s2 = s2, s1\n",
    "        m = len(s2)\n",
    "        mapper = defaultdict(list)\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            mapper[s2[i]].append(i)\n",
    "        nums = []\n",
    "        for c in s1:\n",
    "            if c in mapper:\n",
    "                nums.extend(mapper[c])\n",
    "\n",
    "        return self.longest_increasing_subsequence(nums)\n",
    "\n",
    "    @staticmethod\n",
    "    def longest_increasing_subsequence(nums: List[int]) -> int:\n",
    "        # 使用贪心二分求LIS\n",
    "        stack = []\n",
    "        for x in nums:\n",
    "            idx = bisect_left(stack, x)\n",
    "            if idx < len(stack):\n",
    "                stack[idx] = x\n",
    "            else:\n",
    "                stack.append(x)\n",
    "        # 还可以返回stack获得最长公共子序列\n",
    "        return len(stack)\n",
    "\n",
    "    def longest_common_subsequence_stack(self, s1, s2) -> List[int]:\n",
    "        # 使用LIS的办法求LCS\n",
    "        if len(s1) > len(s2):\n",
    "            s1, s2 = s2, s1\n",
    "        m = len(s2)\n",
    "        mapper = defaultdict(list)\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            mapper[s2[i]].append(i)\n",
    "        nums = []\n",
    "        for c in s1:\n",
    "            if c in mapper:\n",
    "                nums.extend(mapper[c])\n",
    "        # 这里返回的是 s2 的索引不是具体的值\n",
    "        res = self.longest_increasing_subsequence_stack(nums)\n",
    "        return res\n",
    "\n",
    "    @staticmethod\n",
    "    def longest_increasing_subsequence_stack(nums: List[int]) -> List[int]:\n",
    "        # 使用贪心二分求LIS\n",
    "        if not nums:\n",
    "            return []\n",
    "        n = len(nums)\n",
    "        tops = [nums[0]]\n",
    "        piles = [0] * n\n",
    "        piles[0] = 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > tops[-1]:\n",
    "                piles[i] = len(tops)\n",
    "                tops.append(nums[i])\n",
    "            else:\n",
    "                j = bisect.bisect_left(tops, nums[i])\n",
    "                piles[i] = j\n",
    "                tops[j] = nums[i]\n",
    "\n",
    "        lis = []\n",
    "        j = len(tops) - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if piles[i] == j:\n",
    "                lis.append(nums[i])\n",
    "                j -= 1\n",
    "        lis.reverse()  # 反转列表，输出字典序最小的方案\n",
    "        # 还可以返回stack获得最长公共子序列\n",
    "        return lis\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        if len(str1) > len(str2):\n",
    "            str1, str2 = str2, str1\n",
    "        lst2 = LcsLis().longest_common_subsequence_stack(str1, str2)\n",
    "\n",
    "        lst1 = []\n",
    "        i = 0\n",
    "        n = len(str1)\n",
    "        for j in lst2:\n",
    "            w = str2[j]\n",
    "            while str1[i] != w:\n",
    "                i += 1\n",
    "            lst1.append(i)\n",
    "            i += 1\n",
    "\n",
    "        i = j = 0\n",
    "        ans = \"\"\n",
    "        for a, b in zip(lst1, lst2):\n",
    "            while i < a:\n",
    "                ans += str1[i]\n",
    "                i += 1\n",
    "            while j < b:\n",
    "                ans += str2[j]\n",
    "                j += 1\n",
    "            ans +=  str1[i]\n",
    "            i += 1\n",
    "            j += 1\n",
    "        ans += str1[i:]+str2[j:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m, n = len(str1), len(str2)\n",
    "        s = [\"\"] * (n+1)\n",
    "        # 查找公共子序列\n",
    "        for i in range(m):\n",
    "            st = \"\"\n",
    "            for j in range(1, n+1):\n",
    "                stt = s[j]\n",
    "                if str1[i] == str2[j-1]:\n",
    "                    s[j] = st + str1[i]\n",
    "                elif len(s[j-1]) > len(s[j]):\n",
    "                    s[j] = s[j-1]\n",
    "                st = stt\n",
    "        ans = \"\"\n",
    "        # 按照公共子序列切分对齐填入\n",
    "        for i in s[-1]:\n",
    "            x, str1 = str1.split(i, 1)\n",
    "            y, str2 = str2.split(i, 1)\n",
    "            ans += x+y+i \n",
    "        return ans + str1 + str2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m,n=len(str1),len(str2)\n",
    "        #dp=[[[0,\"\"] for _ in range(n+1)]for _ in range(m+1)]\n",
    "        last=[]\n",
    "        now=[[0,\"\"] for _ in range(n+1)]\n",
    "        for i in range(m+1):\n",
    "            last=now\n",
    "            now=[[0,\"\"] for _ in range(n+1)]\n",
    "            for j in range(n+1):\n",
    "                if i==0:\n",
    "                    now[j]=[j,str2[:j]]\n",
    "                elif j==0:\n",
    "                    now[j]=[i,str1[:i]]\n",
    "                elif str1[i-1]==str2[j-1]:\n",
    "                    now[j]=[last[j-1][0]+1,last[j-1][1]+str2[j-1]]\n",
    "                else:\n",
    "                    #print(i,j,dp[i-1][j],dp[i][j-1])\n",
    "                    if last[j][0]>now[j-1][0]:\n",
    "                        now[j]=[now[j-1][0]+1,now[j-1][1]+str2[j-1]]\n",
    "                    else:\n",
    "                        now[j]=[last[j][0]+1,last[j][1]+str1[i-1]]\n",
    "        #for i in range(m+1):\n",
    "        #    print(dp[i])\n",
    "        return now[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        n1, n2 = len(str1), len(str2)\n",
    "        dp = [[0]*(n2+1) for _ in range(n1+1)]\n",
    "        for i in range(n1-1, -1, -1):\n",
    "            for j in range(n2-1, -1, -1):\n",
    "                dp[i][j] = max(dp[i+1][j], dp[i][j+1])\n",
    "                if str1[i] == str2[j]:\n",
    "                    dp[i][j] = max(dp[i][j], 1+dp[i+1][j+1])\n",
    "        res = \"\"\n",
    "        x, y = 0, 0\n",
    "        while not (x == n1 or y == n2):\n",
    "            if dp[x+1][y] == dp[x][y]:\n",
    "                res += str1[x]\n",
    "                x += 1\n",
    "            elif dp[x][y+1] == dp[x][y]:\n",
    "                res += str2[y]\n",
    "                y += 1\n",
    "            else:\n",
    "                res += str1[x]\n",
    "                x += 1\n",
    "                y += 1\n",
    "        if x == n1:\n",
    "            res += str2[y:]\n",
    "        else:\n",
    "            res += str1[x:]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m, n = len(str1), len(str2)\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if str1[i - 1] == str2[j - 1]:\n",
    "                    f[i][j] = f[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    f[i][j] = max(f[i - 1][j], f[i][j - 1])\n",
    "        ans = []\n",
    "        i, j = m, n\n",
    "        while i or j:\n",
    "            if i == 0:\n",
    "                j -= 1\n",
    "                ans.append(str2[j])\n",
    "            elif j == 0:\n",
    "                i -= 1\n",
    "                ans.append(str1[i])\n",
    "            else:\n",
    "                if f[i][j] == f[i - 1][j]:\n",
    "                    i -= 1\n",
    "                    ans.append(str1[i])\n",
    "                elif f[i][j] == f[i][j - 1]:\n",
    "                    j -= 1\n",
    "                    ans.append(str2[j])\n",
    "                else:\n",
    "                    i, j = i - 1, j - 1\n",
    "                    ans.append(str1[i])\n",
    "        return ''.join(ans[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m, n = len(str1), len(str2)\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)] # 最长公共子序列\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if str1[i - 1] == str2[j - 1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        \n",
    "        ans = []\n",
    "        i, j = m, n\n",
    "        while i or j:\n",
    "            if i == 0:\n",
    "                j -= 1\n",
    "                ans.append(str2[j])\n",
    "            elif j == 0:\n",
    "                i -= 1\n",
    "                ans.append(str1[i])\n",
    "            else:\n",
    "                if dp[i][j] == dp[i-1][j]:\n",
    "                    i -= 1\n",
    "                    ans.append(str1[i])\n",
    "                elif dp[i][j] == dp[i][j-1]:\n",
    "                    j -= 1\n",
    "                    ans.append(str2[j])\n",
    "                else:\n",
    "                    i, j = i - 1, j - 1\n",
    "                    ans.append(str1[i])\n",
    "        return ''.join(ans[::-1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, a: str, b: str) -> str:\n",
    "        n, m = len(a), len(b)\n",
    "        f = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                if a[i - 1] == b[j - 1]:\n",
    "                    f[i][j] = f[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    f[i][j] = max(f[i - 1][j], f[i][j - 1])\n",
    "        print(f[n][m])\n",
    "        i, j = n, m\n",
    "        res = \"\"\n",
    "        while i > 0 or j > 0:\n",
    "            if i == 0:\n",
    "                res += b[j - 1]\n",
    "                j -= 1\n",
    "            elif j == 0:\n",
    "                res += a[i - 1]\n",
    "                i -= 1\n",
    "            elif a[i - 1] == b[j - 1]:\n",
    "                res += a[i - 1]\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                if f[i][j] == f[i - 1][j]:\n",
    "                    res += a[i - 1]\n",
    "                    i -= 1\n",
    "                else:\n",
    "                    res += b[j - 1]\n",
    "                    j -= 1\n",
    "        return res[::-1]\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, a: str, b: str) -> str:\n",
    "        n, m = len(a), len(b)\n",
    "        f = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                if a[i - 1] == b[j - 1]:\n",
    "                    f[i][j] = f[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    f[i][j] = max(f[i - 1][j], f[i][j - 1])\n",
    "        print(\"最大公共子序列长度：\", f[n][m])\n",
    "        i, j = n, m\n",
    "        res = \"\"\n",
    "        while i > 0 or j > 0:\n",
    "            if i == 0:\n",
    "                res += b[j - 1]\n",
    "                j -= 1\n",
    "            elif j == 0:\n",
    "                res += a[i - 1]\n",
    "                i -= 1\n",
    "            elif a[i - 1] == b[j - 1]:\n",
    "                res += a[i - 1]\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                if f[i][j] == f[i - 1][j]:\n",
    "                    res += a[i - 1]\n",
    "                    i -= 1\n",
    "                else:\n",
    "                    res += b[j - 1]\n",
    "                    j -= 1\n",
    "        return res[::-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m, n = len(str1), len(str2)\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if str1[i - 1] == str2[j - 1]:\n",
    "                    f[i][j] = f[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    f[i][j] = max(f[i - 1][j], f[i][j - 1])\n",
    "        ans = []\n",
    "        i, j = m, n\n",
    "        while i or j:\n",
    "            if i == 0:\n",
    "                j -= 1\n",
    "                ans.append(str2[j])\n",
    "            elif j == 0:\n",
    "                i -= 1\n",
    "                ans.append(str1[i])\n",
    "            else:\n",
    "                if f[i][j] == f[i - 1][j]:\n",
    "                    i -= 1\n",
    "                    ans.append(str1[i])\n",
    "                elif f[i][j] == f[i][j - 1]:\n",
    "                    j -= 1\n",
    "                    ans.append(str2[j])\n",
    "                else:\n",
    "                    i, j = i - 1, j - 1\n",
    "                    ans.append(str1[i])\n",
    "        return ''.join(ans[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        n, m = len(str1), len(str2)\n",
    "        dp = [[0] * (m+1) for _ in range(n+1)]\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                dp[i][j] = dp[i-1][j-1]+1 if str1[i-1]==str2[j-1] else max(dp[i-1][j], dp[i][j-1])\n",
    "        \n",
    "        res = []\n",
    "        i, j = n, m\n",
    "        while i > 0 or j > 0:\n",
    "            if i == 0:\n",
    "                res.append(str2[j-1])\n",
    "                j -= 1\n",
    "            elif j == 0:\n",
    "                res.append(str1[i-1])\n",
    "                i -= 1\n",
    "            elif dp[i-1][j] == dp[i][j]:\n",
    "                res.append(str1[i-1])\n",
    "                i -= 1\n",
    "            elif dp[i][j-1] == dp[i][j]:\n",
    "                res.append(str2[j-1])\n",
    "                j -= 1\n",
    "            else:\n",
    "                res.append(str1[i-1])\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "        \n",
    "        return ''.join(res)[::-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "\n",
    "        n1 = len(str1)\n",
    "        n2 = len(str2)\n",
    "\n",
    "        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]\n",
    "        \n",
    "\n",
    "\n",
    "        for i in range(1, n1 + 1):\n",
    "            for j in range(1, n2 + 1):\n",
    "                if str1[i - 1] == str2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "\n",
    "        tar = dp[-1][-1]\n",
    "        if tar == 0:\n",
    "            return str1 + str2\n",
    "\n",
    "        i = n1 \n",
    "        j = n2\n",
    "        ans1 = collections.deque([])\n",
    "        ans2 = collections.deque([])\n",
    "        while tar != 0:\n",
    "            if str1[i - 1] == str2[j - 1]:\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "                tar -= 1\n",
    "                ans1.appendleft(i)\n",
    "                ans2.appendleft(j)\n",
    "            else:\n",
    "                if tar == dp[i][j - 1]:\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    i -= 1\n",
    "\n",
    "        ans = []\n",
    "        prev1 = 0\n",
    "        prev2 = 0\n",
    "        for i in range(len(ans1)):\n",
    "            ans.append(str1[prev1:ans1[i]])\n",
    "            ans.append(str2[prev2:ans2[i]])\n",
    "            ans.append(str1[ans1[i]])\n",
    "\n",
    "            prev1 = ans1[i] + 1\n",
    "            prev2 = ans2[i] + 1\n",
    "\n",
    "        \n",
    "        ans.append(str1[prev1:])\n",
    "        ans.append(str2[prev2:])\n",
    "\n",
    "        \n",
    "        return ''.join(ans)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m, n = len(str1), len(str2)\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if str1[i - 1] == str2[j - 1]:\n",
    "                    f[i][j] = f[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    f[i][j] = max(f[i - 1][j], f[i][j - 1])\n",
    "        ans = []\n",
    "        i, j = m, n\n",
    "        while i or j:\n",
    "            if i == 0:\n",
    "                j -= 1\n",
    "                ans.append(str2[j])\n",
    "            elif j == 0:\n",
    "                i -= 1\n",
    "                ans.append(str1[i])\n",
    "            else:\n",
    "                if f[i][j] == f[i - 1][j]:\n",
    "                    i -= 1\n",
    "                    ans.append(str1[i])\n",
    "                elif f[i][j] == f[i][j - 1]:\n",
    "                    j -= 1\n",
    "                    ans.append(str2[j])\n",
    "                else:\n",
    "                    i, j = i - 1, j - 1\n",
    "                    ans.append(str1[i])\n",
    "        return ''.join(ans[::-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m,n = len(str1), len(str2)\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if str1[i] == str2[j]:\n",
    "                    dp[i+1][j+1] = dp[i][j]+1\n",
    "                else:\n",
    "                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])\n",
    "        i, j = m, n\n",
    "        # print(dp[m][n])\n",
    "        sb = []\n",
    "        while i > 0 and j > 0:\n",
    "            if str1[i-1] == str2[j-1]:\n",
    "               sb.append(str1[i-1])\n",
    "               i-=1\n",
    "               j-=1\n",
    "            else:\n",
    "                if dp[i][j] == dp[i-1][j]: #\n",
    "                    sb.append(str1[i-1])\n",
    "                    i-=1\n",
    "                else:\n",
    "                    sb.append(str2[j-1])\n",
    "                    j-=1\n",
    "        while i > 0: \n",
    "            sb.append(str1[i-1])\n",
    "            i-=1\n",
    "        while j > 0:\n",
    "            sb.append(str2[j-1])\n",
    "            j-=1\n",
    "        return ''.join(sb[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        # dp[i][j]: str1前i个char & str2 前j个char 的最长子串的长度\n",
    "        str1, str2 = '#' + str1, '#' + str2\n",
    "        m, n = len(str1), len(str2)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i - 1][j - 1] + 1 if str1[i] == str2[j] else max(dp[i][j - 1], dp[i - 1][j])\n",
    "\n",
    "        ret = []\n",
    "        i, j = m - 1, n - 1\n",
    "        while i > 0 and j > 0:\n",
    "            if str1[i] == str2[j]:\n",
    "                ret.append(str1[i])\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                if dp[i][j] == dp[i][j - 1]:\n",
    "                    ret.append(str2[j])\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    ret.append(str1[i])\n",
    "                    i -= 1\n",
    "\n",
    "        while i > 0:\n",
    "            ret.append(str1[i])\n",
    "            i -= 1\n",
    "        while j > 0:\n",
    "            ret.append(str2[j])\n",
    "            j -= 1\n",
    "\n",
    "        ret.reverse()\n",
    "        return ''.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        \"\"\"\n",
    "        找最长的公共子串，然后利用这个公共子串实现扩充\n",
    "        dp[i][j]代表str1前i个字符和str2前j个字符形成的最长公共子串长度\n",
    "        状态转移方程\n",
    "        str1[i]==str2[j] dp[i][j] = dp[i-1][j-1]+1\n",
    "        str1[i]!=str2[j] dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n",
    "        当dp处理完后，通过双指针得到答案\n",
    "        i和j分别指向两个字符串的尾部\n",
    "        str1[i]==str2[j]时，如果是最长公共子串的字符就加入到答案，并且i j同时前移\n",
    "        dp[i][j]==dp[i-1][j] str1[i]加入到答案 i前移 没有用到str1[i]所以要把答案加进去\n",
    "        dp[i][j]==dp[i][j-1] str1[j]加入到答案 j前移\n",
    "        一旦i j有一个为0则将剩余加入到答案\n",
    "        \"\"\"\n",
    "        m,n = len(str1),len(str2)\n",
    "        dp = [[0 for _ in range(n+1)]for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if str1[i-1]==str2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n",
    "        rs = []\n",
    "        i,j = m,n\n",
    "        while i>0 or j>0:\n",
    "            if i==0:\n",
    "                rs.append(str2[j-1])\n",
    "                j -= 1\n",
    "            elif j==0:\n",
    "                rs.append(str1[i-1])\n",
    "                i -= 1\n",
    "            else:\n",
    "                if str1[i-1]==str2[j-1]:\n",
    "                    rs.append(str2[j-1])\n",
    "                    j -= 1\n",
    "                    i -= 1\n",
    "                elif dp[i][j]==dp[i-1][j]:\n",
    "                    rs.append(str1[i-1])\n",
    "                    i -= 1\n",
    "                else:\n",
    "                    rs.append(str2[j-1])\n",
    "                    j -= 1\n",
    "        return \"\".join(rs[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        # dp[i][j]: str1前i个char & str2 前j个char 的最长子串的长度\n",
    "        str1, str2 = '#' + str1, '#' + str2\n",
    "        m, n = len(str1), len(str2)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i - 1][j - 1] + 1 if str1[i] == str2[j] else max(dp[i][j - 1], dp[i - 1][j])\n",
    "\n",
    "        ret = []\n",
    "        i, j = m - 1, n - 1\n",
    "        while i > 0 and j > 0:\n",
    "            if str1[i] == str2[j]:\n",
    "                ret.append(str1[i])\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                if dp[i][j] == dp[i][j - 1]:\n",
    "                    ret.append(str2[j])\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    ret.append(str1[i])\n",
    "                    i -= 1\n",
    "\n",
    "        while i > 0:\n",
    "            ret.append(str1[i])\n",
    "            i -= 1\n",
    "        while j > 0:\n",
    "            ret.append(str2[j])\n",
    "            j -= 1\n",
    "\n",
    "        ret.reverse()\n",
    "        return ''.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m, n = len(str1), len(str2)\n",
    "        dp = [[0 for i in range(n + 1)] for j in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if str1[i - 1] == str2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "        i, j = m, n\n",
    "        ans = []\n",
    "        while i > 0 or j > 0:\n",
    "            if i == 0:\n",
    "                ans.append(str2[j - 1])\n",
    "                j -= 1\n",
    "            elif j == 0:\n",
    "                ans.append(str1[i - 1])\n",
    "                i -= 1\n",
    "            else:\n",
    "                # dp[i][j] == dp[i - 1][j -1]的情况要放最后\n",
    "                if dp[i][j] == dp[i - 1][j]:\n",
    "                    ans.append(str1[i - 1])\n",
    "                    i -= 1\n",
    "                elif dp[i][j] == dp[i][j - 1]:\n",
    "                    ans.append(str2[j - 1])\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    ans.append(str1[i - 1])\n",
    "                    i -= 1\n",
    "                    j -= 1\n",
    "        return \"\".join(ans[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m = len(str1)\n",
    "        n = len(str2)\n",
    "\n",
    "        l = [[0]*n for _ in range(m)]\n",
    "        l[0][0] = int(str1[0] == str2[0])\n",
    "        for i in range(1, n):\n",
    "            l[0][i] = l[0][i-1] if l[0][i-1] else int(str1[0] == str2[i])\n",
    "\n",
    "        for i in range(1, m):\n",
    "            l[i][0] = l[i-1][0] if l[i-1][0] else int(str1[i] == str2[0])\n",
    "\n",
    "        dp = [None]*n\n",
    "        dp[0] = str1[0] if str1[0] == str2[0] else str1[0]+str2[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = str2[:i+1] if str1[0] in str2[:i+1] else str1[0]+str2[:i+1]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            dp1 = [None]*n\n",
    "            dp1[0] = str1[:i+1] if str2[0] in str1[:i+1] else str1[:i+1]+str2[0]\n",
    "            for j in range(1, n):\n",
    "                l[i][j] = 1+l[i-1][j-1] if str1[i] == str2[j] else max(l[i-1][j], l[i][j-1])\n",
    "                dp1[j] = dp[j-1]+str1[i] if str1[i] == str2[j] else (dp[j]+str1[i] if l[i-1][j]>l[i][j-1] else dp1[j-1]+str2[j])\n",
    "            dp = dp1\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        l1 = len(str1)\n",
    "        l2 = len(str2)\n",
    "        \n",
    "        # Find LCS using dynamic programming\n",
    "        dp = [[\"\"] * (l2 + 1) for _ in range(l1 + 1)]\n",
    "        for i in range(1, l1 + 1):\n",
    "            for j in range(1, l2 + 1):\n",
    "                if str1[i-1] == str2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + str1[i-1]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=len)\n",
    "        \n",
    "        lcs = dp[l1][l2]\n",
    "        \n",
    "        # Build the shortest common supersequence using the LCS\n",
    "        ans = []\n",
    "        p1, p2 = 0, 0\n",
    "        \n",
    "        for char in lcs:\n",
    "            while str1[p1] != char:\n",
    "                ans.append(str1[p1])\n",
    "                p1 += 1\n",
    "            while str2[p2] != char:\n",
    "                ans.append(str2[p2])\n",
    "                p2 += 1\n",
    "            ans.append(char)\n",
    "            p1 += 1\n",
    "            p2 += 1\n",
    "        \n",
    "        # Append the remaining parts of str1 and str2\n",
    "        ans.extend(str1[p1:])\n",
    "        ans.extend(str2[p2:])\n",
    "        \n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        n1, n2 = len(str1), len(str2)\n",
    "        lcm = [['' for _ in range(n2 + 1)] for _ in range(n1 + 1)]\n",
    "        for i in range(1, n1 + 1):\n",
    "            for j in range(1, n2 + 1):\n",
    "                if str1[i - 1] == str2[j - 1]:\n",
    "                    lcm[i][j] = lcm[i - 1][j - 1] + str1[i - 1]\n",
    "                else:\n",
    "                    if len(lcm[i - 1][j]) > len(lcm[i][j - 1]):\n",
    "                        lcm[i][j] = lcm[i - 1][j]\n",
    "                    else:\n",
    "                        lcm[i][j] = lcm[i][j - 1]\n",
    "        i, j = 0, 0 \n",
    "        res = ''\n",
    "        common = lcm[-1][-1]\n",
    "        for c in common:\n",
    "            while i < n1 and str1[i] != c:\n",
    "                res += str1[i]\n",
    "                i += 1 \n",
    "            while j < n2 and str2[j] != c:\n",
    "                res += str2[j]\n",
    "                j += 1 \n",
    "            res += c\n",
    "            i += 1 \n",
    "            j += 1 \n",
    "        while i < n1:\n",
    "            res += str1[i]\n",
    "            i += 1 \n",
    "        while j < n2:\n",
    "            res += str2[j]\n",
    "            j += 1 \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m,n=len(str1),len(str2)\n",
    "        dp=[[0]*(n+1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if str1[i]==str2[j]:\n",
    "                    dp[i+1][j+1]=dp[i][j]+1\n",
    "                else:\n",
    "                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])\n",
    "        \n",
    "        print(dp)\n",
    "        res=[]\n",
    "        i,j=m-1,n-1\n",
    "        while i>=0 and j>=0:\n",
    "            if str1[i]==str2[j]:\n",
    "                res.append(str1[i])\n",
    "                i-=1;j-=1\n",
    "            else:\n",
    "                if dp[i][j+1]<dp[i+1][j]:                   \n",
    "                    res.append(str2[j])\n",
    "                    j-=1\n",
    "                else:                    \n",
    "                    res.append(str1[i])\n",
    "                    i-=1\n",
    "        while i>=0:\n",
    "            res.append(str1[i])\n",
    "            i-=1\n",
    "        while j>=0:\n",
    "            res.append(str2[j])\n",
    "            j-=1\n",
    "\n",
    "        return \"\".join(res[::-1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m,n=len(str1),len(str2)\n",
    "        dp=[[0]*(n+1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if str1[i]==str2[j]:\n",
    "                    dp[i+1][j+1]=dp[i][j]+1\n",
    "                else:\n",
    "                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])\n",
    "        \n",
    "        print(dp)\n",
    "        res=[]\n",
    "        i,j=m-1,n-1\n",
    "        while i>=0 and j>=0:\n",
    "            if str1[i]==str2[j]:\n",
    "                res.append(str1[i])\n",
    "                i-=1;j-=1\n",
    "            else:\n",
    "                if dp[i][j+1]<dp[i+1][j]:                   \n",
    "                    res.append(str2[j])\n",
    "                    j-=1\n",
    "                else:                    \n",
    "                    res.append(str1[i])\n",
    "                    i-=1\n",
    "        while i>=0:\n",
    "            res.append(str1[i])\n",
    "            i-=1\n",
    "        while j>=0:\n",
    "            res.append(str2[j])\n",
    "            j-=1\n",
    "        return \"\".join(res[::-1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        l1 = len(str1)\n",
    "        l2 = len(str2)\n",
    "        if l1 < l2:\n",
    "            l1,l2 = l2,l1\n",
    "            str1,str2 = str2,str1\n",
    "        res = ''\n",
    "        dp = [[0] * (l2 + 1) for _ in range(l1 + 1)]\n",
    "        res = [[''] * (l2 + 1) for _ in range(l1 + 1)]\n",
    "        for i in range(l1):\n",
    "            for j in range(l2):\n",
    "                if str1[i] == str2[j]:\n",
    "                    if dp[i][j] + 1 > dp[i + 1][j + 1]:\n",
    "                        dp[i + 1][j + 1] = dp[i][j] + 1\n",
    "                        res[i + 1][j + 1] = res[i][j] + str1[i]\n",
    "                    \n",
    "                else:\n",
    "                    dp[i + 1][j + 1] = max(dp[i + 1][j],dp[i][j + 1])\n",
    "                    if len(res[i + 1][j]) > len(res[i][j + 1]):\n",
    "                        res[i + 1][j + 1] = res[i + 1][j]\n",
    "                    else:\n",
    "                        res[i + 1][j + 1] = res[i][j + 1]\n",
    "        lcs = res[-1][-1]\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "        ans = []\n",
    "        for char in lcs:\n",
    "            while str1[p1] != char:\n",
    "                ans.append(str1[p1])\n",
    "                p1 += 1\n",
    "            while str2[p2] != char:\n",
    "                ans.append(str2[p2])\n",
    "                p2 += 1\n",
    "            ans.append(char)\n",
    "            p1 += 1\n",
    "            p2 += 1\n",
    "        ans.extend(str1[p1:])\n",
    "        ans.extend(str2[p2:])\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        n=len(str1)\n",
    "        m=len(str2)\n",
    "        dp=[[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if str1[i]==str2[j]:\n",
    "                    dp[i+1][j+1]=max(dp[i][j],dp[i+1][j+1])+1\n",
    "                else:\n",
    "                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])\n",
    "        i=n-1\n",
    "        j=m-1\n",
    "        ans=[]\n",
    "        while i>=0 and j>=0:\n",
    "            if str1[i]==str2[j]:\n",
    "                ans.append(str1[i])\n",
    "                i-=1\n",
    "                j-=1\n",
    "            elif dp[i+1][j+1]==dp[i][j+1]:\n",
    "                ans.append(str1[i])\n",
    "                i-=1\n",
    "            else:\n",
    "                ans.append(str2[j])\n",
    "                j-=1\n",
    "        if i>=0:\n",
    "            while i>=0:\n",
    "                ans.append(str1[i])\n",
    "                i-=1\n",
    "        else:\n",
    "            while j>=0:\n",
    "                ans.append(str2[j])\n",
    "                j-=1\n",
    "        return ''.join(reversed(ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        n=len(str1)\n",
    "        m=len(str2)\n",
    "        dp=[[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if str1[i]==str2[j]:\n",
    "                    dp[i+1][j+1]=max(dp[i][j],dp[i+1][j+1])+1\n",
    "                else:\n",
    "                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])\n",
    "        i=n-1\n",
    "        j=m-1\n",
    "        ans=[]\n",
    "        while i>=0 and j>=0:\n",
    "            if str1[i]==str2[j]:\n",
    "                ans.append(str1[i])\n",
    "                i-=1\n",
    "                j-=1\n",
    "            elif dp[i+1][j+1]==dp[i][j+1]:\n",
    "                ans.append(str1[i])\n",
    "                i-=1\n",
    "            else:\n",
    "                ans.append(str2[j])\n",
    "                j-=1\n",
    "        return str1[:i+1]+str2[:j+1]+''.join(reversed(ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        n1,n2=len(str1),len(str2)\n",
    "        dp=[[n1+n2]*(n2+1) for _ in range(n1+1)]\n",
    "        dp[0][0]=0\n",
    "        for i in range(1,n1+1):\n",
    "            dp[i][0]=i\n",
    "        for i in range(1,n2+1):\n",
    "            dp[0][i]=i\n",
    "\n",
    "        for i in range(1,n1+1):\n",
    "            for j in range(1,n2+1):\n",
    "                if str1[i-1]==str2[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i][j-1],dp[i-1][j])+1\n",
    "        #print(dp)\n",
    "        ans=''\n",
    "        i,j=n1-1,n2-1\n",
    "        \n",
    "        while i>=0 and j>=0:\n",
    "            if str1[i]==str2[j]:\n",
    "                ans+=str1[i]\n",
    "                i-=1\n",
    "                j-=1\n",
    "            elif dp[i+1][j+1]==dp[i][j+1]+1:\n",
    "                ans+=str1[i]\n",
    "                i-=1\n",
    "            elif dp[i+1][j+1]==dp[i+1][j]+1:\n",
    "                ans+=str2[j]\n",
    "                j-=1\n",
    "       # print('ans',ans,'i',i,'j',j)\n",
    "        \n",
    "        \n",
    "        return str1[:i+1]+str2[:j+1]+ans[::-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, s: str, t: str) -> str:\n",
    "        n, m = len(s), len(t)\n",
    "        # f[i+1][j+1] 表示 s 的前 i 个字母和 t 的前 j 个字母的最短公共超序列的长度\n",
    "        f = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        f[0] = list(range(m + 1))  # 递归边界 f[0][j] = j\n",
    "        for i in range(1, n + 1):\n",
    "            f[i][0] = i  # 递归边界\n",
    "        for i, x in enumerate(s):\n",
    "            for j, y in enumerate(t):\n",
    "                if x == y:  # 最短公共超序列一定包含 s[i]\n",
    "                    f[i + 1][j + 1] = f[i][j] + 1\n",
    "                else:  # 取更短的组成答案\n",
    "                    f[i + 1][j + 1] = min(f[i][j + 1], f[i + 1][j]) + 1\n",
    "\n",
    "        ans = []\n",
    "        i, j = n - 1, m - 1\n",
    "        while i >= 0 and j >= 0:\n",
    "            if s[i] == t[j]:  # 公共超序列一定包含 s[i]\n",
    "                ans.append(s[i])\n",
    "                i -= 1\n",
    "                j -= 1  # 相当于继续递归 make_ans(i - 1, j - 1)\n",
    "            elif f[i + 1][j + 1] == f[i][j + 1] + 1:\n",
    "                ans.append(s[i])\n",
    "                i -= 1  # 相当于继续递归 make_ans(i - 1, j)\n",
    "            else:\n",
    "                ans.append(t[j])\n",
    "                j -= 1  # 相当于继续递归 make_ans(i, j - 1)\n",
    "\n",
    "        # 补上前面的递归边界\n",
    "        # reversed(ans) 也可以写成 ans[::-1]\n",
    "        return s[:i + 1] + t[:j + 1] + ''.join(reversed(ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "\n",
    "        m, n = len(str1), len(str2)\n",
    "\n",
    "        dp = [[inf] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m + 1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(n + 1):\n",
    "            dp[0][i] = i\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if str1[i - 1] == str2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    if dp[i][j - 1] < dp[i - 1][j]:\n",
    "                        dp[i][j] = dp[i][j - 1] + 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j] + 1\n",
    "        i, j = m, n\n",
    "        ans = []\n",
    "        while i > 0 and j > 0:\n",
    "            if str1[i - 1] == str2[j - 1]:\n",
    "                ans.append(str1[i - 1])\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                if dp[i][j] == dp[i - 1][j]:\n",
    "                    ans.append(str2[j - 1])\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    ans.append(str1[i - 1])\n",
    "                    i -= 1\n",
    "        # print(i, j, ans, dp[m][n])\n",
    "        while i > 0:\n",
    "            ans.append(str1[i - 1])\n",
    "            i -= 1\n",
    "        while j > 0:\n",
    "            ans.append(str2[j - 1])\n",
    "            j -= 1\n",
    "        return ''.join(ans[::-1])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\r\n",
    "        m, n = len(str1), len(str2)\r\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\r\n",
    "        for i in range(m + 1):\r\n",
    "            dp[i][0] = i \r\n",
    "        for j in range(n + 1):\r\n",
    "            dp[0][j] = j \r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if str1[i] == str2[j]:\r\n",
    "                    dp[i + 1][j + 1] = dp[i][j] + 1 \r\n",
    "                else:\r\n",
    "                    dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j]) + 1 \r\n",
    "        res = []\r\n",
    "        x, y = m, n \r\n",
    "        while x > 0 and y > 0:\r\n",
    "            if str1[x - 1] == str2[y - 1]:\r\n",
    "                res.append(str1[x - 1])  \r\n",
    "                x -= 1\r\n",
    "                y -= 1\r\n",
    "            elif dp[x][y] == dp[x - 1][y] + 1:\r\n",
    "                res.append(str1[x - 1])\r\n",
    "                x -= 1\r\n",
    "            else:\r\n",
    "                res.append(str2[y - 1]) \r\n",
    "                y -= 1 \r\n",
    "        while x > 0:\r\n",
    "            res.append(str1[x - 1])\r\n",
    "            x -= 1\r\n",
    "        while y:\r\n",
    "            res.append(str2[y - 1])\r\n",
    "            y -= 1 \r\n",
    "        return \"\".join(res)[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m = len(str1)\n",
    "        n = len(str2)\n",
    "\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        f[0] = list(range(n + 1))  # 递归边界 f[0][j] = j\n",
    "        for i in range(1, m + 1):\n",
    "            f[i][0] = i  # 递归边界\n",
    "        for i,x in enumerate(str1):\n",
    "            for j,y in enumerate(str2):\n",
    "                if x == y:\n",
    "                    f[i+1][j+1] = f[i][j]+1\n",
    "                else:\n",
    "                    f[i+1][j+1] = min(f[i+1][j],f[i][j+1])+1\n",
    "        ans = []\n",
    "        i, j = m - 1, n - 1\n",
    "        while i >= 0 and j >= 0:\n",
    "            if str1[i] == str2[j]:  # 公共超序列一定包含 s[i]\n",
    "                ans.append(str1[i])\n",
    "                i -= 1\n",
    "                j -= 1  # 相当于继续递归 make_ans(i - 1, j - 1)\n",
    "            elif f[i + 1][j + 1] == f[i][j + 1] + 1:\n",
    "                ans.append(str1[i])\n",
    "                i -= 1  # 相当于继续递归 make_ans(i - 1, j)\n",
    "            else:\n",
    "                ans.append(str2[j])\n",
    "                j -= 1  # 相当于继续递归 make_ans(i, j - 1)\n",
    "\n",
    "        # 补上前面的递归边界\n",
    "        # reversed(ans) 也可以写成 ans[::-1]\n",
    "        return str1[:i + 1] + str2[:j + 1] + ''.join(reversed(ans))\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # @cache \n",
    "        # def dfs(i,j):\n",
    "        #     if i==m:\n",
    "        #         # print(i,j,str2[j:])\n",
    "        #         return str2[j:]\n",
    "        #     if j==n:\n",
    "        #         # print(i,j,str1[i:])\n",
    "        #         return str1[i:]\n",
    "        #     if str1[i] == str2[j]:\n",
    "        #         return str1[i]+dfs(i+1,j+1)\n",
    "        #     else:\n",
    "        #         ans1 = str1[i]+dfs(i+1,j)\n",
    "        #         ans2 = str2[j]+dfs(i,j+1)\n",
    "        #         if len(ans1) >= len(ans2):\n",
    "        #             return ans2\n",
    "        #         else:\n",
    "        #             return ans1\n",
    "        # return dfs(0,0)\n",
    "\n",
    "\n",
    "        # @cache \n",
    "        # def dfs(i,j):\n",
    "        #     if i==m:\n",
    "        #         # print(i,j,str2[j:])\n",
    "        #         return str2[j:]\n",
    "        #     if j==n:\n",
    "        #         # print(i,j,str1[i:])\n",
    "        #         return str1[i:]\n",
    "        #     if str1[i] == str2[j]:\n",
    "        #         return str1[i]+dfs(i+1,j+1)\n",
    "        #     else:\n",
    "        #         ans1 = str1[i]+dfs(i+1,j)\n",
    "        #         ans2 = str2[j]+dfs(i,j+1)\n",
    "        #         if len(ans1) >= len(ans2):\n",
    "        #             return ans2\n",
    "        #         else:\n",
    "        #             return ans1\n",
    "        # return dfs(0,0)\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        dp = [[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "\n",
    "        m, n = len(str1), len(str2)\n",
    "\n",
    "        dp = [[inf] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m + 1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(n + 1):\n",
    "            dp[0][i] = i\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if str1[i - 1] == str2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    if dp[i][j - 1] < dp[i - 1][j]:\n",
    "                        dp[i][j] = dp[i][j - 1] + 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j] + 1\n",
    "        i, j = m, n\n",
    "        ans = []\n",
    "        while i > 0 and j > 0:\n",
    "            if str1[i - 1] == str2[j - 1]:\n",
    "                ans.append(str1[i - 1])\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                if dp[i][j] == dp[i - 1][j] + 1:\n",
    "                    ans.append(str1[i - 1])\n",
    "                    i -= 1\n",
    "                else:\n",
    "                    ans.append(str2[j - 1])\n",
    "                    j -= 1\n",
    "        # print(i, j, ans, dp[m][n])\n",
    "        while i > 0:\n",
    "            ans.append(str1[i - 1])\n",
    "            i -= 1\n",
    "        while j > 0:\n",
    "            ans.append(str2[j - 1])\n",
    "            j -= 1\n",
    "        return ''.join(ans[::-1])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        n, m = len(str1), len(str2)\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            dp[i][m] = n - i\n",
    "        for j in range(m):\n",
    "            dp[n][j] = m - j\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(m-1, -1, -1):\n",
    "                if str1[i] == str2[j]:\n",
    "                    dp[i][j] = dp[i+1][j+1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i+1][j], dp[i][j+1]) + 1\n",
    "\n",
    "        res = \"\"\n",
    "        t1, t2 = 0, 0\n",
    "        while t1 < n and t2 < m:\n",
    "            if str1[t1] == str2[t2]:\n",
    "                res += str1[t1]\n",
    "                t1 += 1\n",
    "                t2 += 1\n",
    "            elif dp[t1+1][t2] == dp[t1][t2] - 1:\n",
    "                res += str1[t1]\n",
    "                t1 += 1\n",
    "            elif dp[t1][t2+1] == dp[t1][t2] - 1:\n",
    "                res += str2[t2]\n",
    "                t2 += 1\n",
    "        res += str1[t1:] if t1 < n else str2[t2:]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "\n",
    "        m, n = len(str1), len(str2)\n",
    "\n",
    "        dp = [[inf] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m + 1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(n + 1):\n",
    "            dp[0][i] = i\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if str1[i - 1] == str2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    if dp[i][j - 1] < dp[i - 1][j]:\n",
    "                        dp[i][j] = dp[i][j - 1] + 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j] + 1\n",
    "        i, j = m, n\n",
    "        ans = []\n",
    "        while i > 0 and j > 0:\n",
    "            if str1[i - 1] == str2[j - 1]:\n",
    "                ans.append(str1[i - 1])\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                if dp[i][j] == dp[i - 1][j]:\n",
    "                    ans.append(str2[j - 1])\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    ans.append(str1[i - 1])\n",
    "                    i -= 1\n",
    "        # print(i, j, ans, dp[m][n])\n",
    "        while i > 0:\n",
    "            ans.append(str1[i - 1])\n",
    "            i -= 1\n",
    "        while j > 0:\n",
    "            ans.append(str2[j - 1])\n",
    "            j -= 1\n",
    "        return ''.join(ans[::-1])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        n1,n2=len(str1),len(str2)\n",
    "        dp=[[n1+n2]*(n2+1) for _ in range(n1+1)]\n",
    "        dp[0][0]=0\n",
    "        for i in range(1,n1+1):\n",
    "            dp[i][0]=i\n",
    "        for i in range(1,n2+1):\n",
    "            dp[0][i]=i\n",
    "\n",
    "        for i in range(1,n1+1):\n",
    "            for j in range(1,n2+1):\n",
    "                if str1[i-1]==str2[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i][j-1],dp[i-1][j])+1\n",
    "        #print(dp)\n",
    "        ans=''\n",
    "        i,j=n1,n2\n",
    "        \n",
    "        while i>0 or j>0:\n",
    "            if i==0:\n",
    "                ans+=str2[j-1]\n",
    "                j-=1\n",
    "            elif j==0:\n",
    "                ans+=str1[i-1]\n",
    "                i-=1\n",
    "            elif str1[i-1]==str2[j-1]:\n",
    "                ans+=str1[i-1]\n",
    "                i-=1\n",
    "                j-=1\n",
    "            elif dp[i][j]==dp[i-1][j]+1:\n",
    "                ans+=str1[i-1]\n",
    "                i-=1\n",
    "            else:#if dp[i][j]==dp[i][j-1]\n",
    "                ans+=str2[j-1]\n",
    "                j-=1\n",
    "       # print('ans',ans,'i',i,'j',j)\n",
    "        \n",
    "        \n",
    "        return ans[::-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        n, m = len(str1), len(str2)\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(m + 1):\n",
    "            dp[0][i] = i\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                if str1[i - 1] == str2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1\n",
    "        i, j = n, m\n",
    "        ret = []\n",
    "        while i > 0 and j > 0:\n",
    "            if str1[i - 1] == str2[j - 1]:\n",
    "                ret.append(str1[i - 1])\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            elif dp[i - 1][j] + 1 == dp[i][j]:\n",
    "                ret.append(str1[i - 1])\n",
    "                i -= 1\n",
    "            else:\n",
    "                ret.append(str2[j - 1])\n",
    "                j -= 1\n",
    "        ans = \"\".join(ret[::-1])\n",
    "        if i > 0:\n",
    "            ans = str1[:i] + ans\n",
    "        elif j > 0:\n",
    "            ans = str2[:j] + ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        \n",
    "        '''\n",
    "        例如 abac 与 cab, 结果是cabac\n",
    "        对于结果中的任意字符, 只能属于str1一次, 但是也可以同时属于str1和str2\n",
    "        \n",
    "        '''\n",
    "        \n",
    "        N1 = len(str1)\n",
    "        N2 = len(str2)\n",
    "        \n",
    "        dp = [[inf] * (N2+1) for _ in range(N1+1)]\n",
    "        \n",
    "        for i in range(N1+1):\n",
    "            for j in range(N2+1):\n",
    "                if i == 0 or j == 0:\n",
    "                    dp[i][j] = i + j\n",
    "        \n",
    "        for i in range(N1):\n",
    "            for j in range(N2):\n",
    "                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j+1]+1, dp[i+1][j]+1)\n",
    "                if str1[i] == str2[j]:\n",
    "                    dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+1)\n",
    "        \n",
    "        ans = []\n",
    "        i, j = N1, N2\n",
    "        while i >0 or j>0:\n",
    "            if i == 0:\n",
    "                ans.append(str2[j-1])\n",
    "                j -= 1\n",
    "            elif j == 0:\n",
    "                ans.append(str1[i-1])\n",
    "                i -= 1\n",
    "            elif dp[i][j] == dp[i-1][j] + 1:\n",
    "                ans.append(str1[i-1])\n",
    "                i -= 1\n",
    "            elif dp[i][j] == dp[i][j-1] + 1:\n",
    "                ans.append(str2[j-1])\n",
    "                j -= 1\n",
    "            else:\n",
    "                ans.append(str1[i-1])\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            \n",
    "        \n",
    "        return \"\".join(ans[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, s: str, t: str) -> str:\n",
    "        n, m = len(s), len(t)\n",
    "        f = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        f[0] = list(range(m + 1)) # 递归边界f[0][j] = j\n",
    "        for i in range(1, n + 1):\n",
    "            f[i][0] = i\n",
    "        for i, x in enumerate(s):\n",
    "            for j, y in enumerate(t):\n",
    "                if x == y:\n",
    "                    f[i + 1][j + 1] = f[i][j] + 1\n",
    "                else:\n",
    "                    f[i + 1][j + 1] = min(f[i][j + 1], f[i + 1][j]) + 1\n",
    "        \n",
    "        ans = []\n",
    "        i, j = n - 1, m - 1\n",
    "        while i >= 0 and j >= 0:\n",
    "            if s[i] == t[j]:\n",
    "                ans.append(s[i])\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            elif f[i + 1][j + 1] == f[i][j + 1] + 1:\n",
    "                ans.append(s[i])\n",
    "                i -= 1\n",
    "            else:\n",
    "                ans.append(t[j])\n",
    "                j -= 1\n",
    "        \n",
    "        return s[:i + 1] + t[:j + 1] + ''.join(ans[::-1])\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        len1, len2 = len(str1), len(str2)\n",
    "        dp = [[0 for _ in range(len2+1)] for _ in range(len1+1)]\n",
    "        \n",
    "        for i in range(len1+1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(len2+1):\n",
    "            dp[0][i] = i\n",
    "\n",
    "        for i in range(1, len1+1):\n",
    "            for j in range(1, len2+1):\n",
    "                if str1[i-1] == str2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1)\n",
    "        \n",
    "        s = ''\n",
    "        i_idx, j_idx = len1, len2\n",
    "        for i in range(dp[i_idx][j_idx]):\n",
    "            if dp[i_idx][j_idx] == dp[i_idx][j_idx-1] + 1:\n",
    "                s = str2[j_idx-1] + s\n",
    "                j_idx -= 1\n",
    "            elif dp[i_idx][j_idx] == dp[i_idx-1][j_idx] + 1:\n",
    "                s = str1[i_idx-1] + s\n",
    "                i_idx -= 1\n",
    "            else:\n",
    "                s = str1[i_idx-1] + s\n",
    "                i_idx -= 1\n",
    "                j_idx -= 1\n",
    "                \n",
    "        \n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        n1=len(str1)\n",
    "        n2=len(str2)\n",
    "        dp=[[0 for i in range(n1+1)]for i in range(n2+1)]\n",
    "        ans=0\n",
    "        for i in range(1,n1+1):\n",
    "            dp[0][i]=i\n",
    "        for i in range(1,n2+1):\n",
    "            dp[i][0]=i\n",
    "        for i in range(0,n1):\n",
    "            for j in range(0,n2):\n",
    "                if str1[i]==str2[j]:\n",
    "                    dp[j+1][i+1]=dp[j][i]+1\n",
    "                else:\n",
    "                    dp[j+1][i+1]=min(dp[j][i+1],dp[j+1][i])+1\n",
    "        ans=[]\n",
    "        i=n1-1\n",
    "        j=n2-1\n",
    "        while i>=0 and j>=0:\n",
    "            if str1[i]==str2[j]:\n",
    "                ans.append(str1[i])\n",
    "                i-=1\n",
    "                j-=1\n",
    "            elif dp[j+1][i+1]==dp[j][i+1]+1:\n",
    "                ans.append(str2[j])\n",
    "                j-=1\n",
    "            else:\n",
    "                ans.append(str1[i])\n",
    "                i-=1\n",
    "        return str1[:i+1]+str2[:j+1]+''.join(reversed(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        m, n = len(str1), len(str2)\n",
    "        dp = [[0 for _ in range(n+1)]for _ in range(m+1)]\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            dp[i][0] = i \n",
    "        for i in range(1, n+1):\n",
    "            dp[0][i] = i \n",
    "        \n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                s1, s2 = str1[i-1], str2[j-1]\n",
    "                if s1 == s2:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1])+1\n",
    "        res = ''\n",
    "        i, j = m-1, n-1\n",
    "        while i >= 0 and j >= 0:\n",
    "            if str1[i] == str2[j]:\n",
    "                res = str1[i] + res\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                if dp[i][j+1] <= dp[i+1][j]:\n",
    "                    res = str1[i] + res \n",
    "                    i -= 1\n",
    "                else:\n",
    "                    res = str2[j] + res\n",
    "                    j -= 1\n",
    "        if i >= 0:\n",
    "            res = str1[:i+1] + res \n",
    "        if j >= 0:\n",
    "            res = str2[:j+1] + res \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str: \n",
    "        n, m = len(str1), len(str2) \n",
    "        f = [[0] * (m+1) for _ in range(n+1)]\n",
    "        g = [[None] * (m+1) for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                if str1[i-1] == str2[j-1]:\n",
    "                    f[i][j] = f[i-1][j-1] + 1\n",
    "                    g[i][j] = (i-1, j-1)\n",
    "                else:\n",
    "                    if f[i-1][j] >= f[i][j-1]:\n",
    "                        f[i][j] = f[i-1][j]\n",
    "                        g[i][j] = (i-1, j) \n",
    "                    else:\n",
    "                        f[i][j] = f[i][j-1]\n",
    "                        g[i][j] = (i, j-1) \n",
    "        a = [n]\n",
    "        b = [m]\n",
    "        x,y = n, m \n",
    "        while x > 0 and y > 0:\n",
    "            px,py = g[x][y]\n",
    "            if f[x][y] == f[px][py]:\n",
    "                x, y = px, py \n",
    "            else:\n",
    "                a.append(x-1)\n",
    "                b.append(y-1) \n",
    "                x, y = px, py \n",
    "\n",
    "        i, j = 0, 0\n",
    "        ans = [] \n",
    "        while i <n and j < m:\n",
    "            while i < n and i < a[-1]:\n",
    "                ans.append(str1[i]) \n",
    "                i+=1 \n",
    "            while j < m and j < b[-1]:\n",
    "                ans.append(str2[j])\n",
    "                j+=1 \n",
    "            if i < n:\n",
    "                ans.append(str1[i]) \n",
    "            i+=1\n",
    "            j+=1\n",
    "            a.pop() \n",
    "            b.pop() \n",
    "        while i < n:\n",
    "            while i < n and i <= a[-1]:\n",
    "                ans.append(str1[i]) \n",
    "                i+=1\n",
    "            a.pop() \n",
    "        while j < m:\n",
    "            while j < m and j <= b[-1]:\n",
    "                ans.append(str2[j])\n",
    "                j+=1\n",
    "            b.pop()\n",
    "\n",
    "        return ''.join(ans) \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, s: str, t: str) -> str:\n",
    "        # 这里在最后加个标志位，以便于s,t的公共子序列覆盖到s和t的最后一位\n",
    "        # 方便下面计算答案\n",
    "        s += '0'\n",
    "        t += '0'\n",
    "        n, m = len(s), len(t)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0:\n",
    "                return ''\n",
    "            if s[i] == t[j]:\n",
    "                return dfs(i - 1, j - 1) + s[i]\n",
    "            else:\n",
    "                p, q = dfs(i - 1, j), dfs(i, j - 1)\n",
    "                return p if len(p) > len(q) else  q\n",
    "        # 最长公共子序列\n",
    "        w = dfs(n - 1, m - 1)\n",
    "\n",
    "        ans = []\n",
    "        i = j = 0\n",
    "        for x in w:\n",
    "            while t[j] != x:\n",
    "                ans.append(t[j])\n",
    "                j += 1\n",
    "            while s[i] != x:\n",
    "                ans.append(s[i])\n",
    "                i += 1\n",
    "            ans.append(x)\n",
    "            i += 1\n",
    "            j += 1\n",
    "        ans.pop()   # 将之前加入的0弹出去\n",
    "        return ''.join(ans) # 这里直接返回ans也可以 小bug 哈哈"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, s: str, t: str) -> str:\n",
    "        # 这里在最后加个标志位，以便于s,t的公共子序列覆盖到s和t的最后一位\n",
    "        # 方便下面计算答案\n",
    "        s += '0'\n",
    "        t += '0'\n",
    "        n, m = len(s), len(t)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0:\n",
    "                return ''\n",
    "            if s[i] == t[j]:\n",
    "                return dfs(i - 1, j - 1) + s[i]\n",
    "            else:\n",
    "                p, q = dfs(i - 1, j), dfs(i, j - 1)\n",
    "                return p if len(p) > len(q) else  q\n",
    "        # 最长公共子序列\n",
    "        w = dfs(n - 1, m - 1)\n",
    "\n",
    "        ans = []\n",
    "        i = j = 0\n",
    "        for x in w:\n",
    "            while t[j] != x:\n",
    "                ans.append(t[j])\n",
    "                j += 1\n",
    "            while s[i] != x:\n",
    "                ans.append(s[i])\n",
    "                i += 1\n",
    "            ans.append(x)\n",
    "            i += 1\n",
    "            j += 1\n",
    "        ans.pop()   # 将之前加入的0弹出去\n",
    "        return ''.join(ans) # 这里直接返回ans也可以 小bug 哈哈"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        \n",
    "        '''\n",
    "        例如 abac 与 cab, 结果是cabac\n",
    "        对于结果中的任意字符, 只能属于str1一次, 但是也可以同时属于str1和str2\n",
    "        \n",
    "        '''\n",
    "        \n",
    "        N1 = len(str1)\n",
    "        N2 = len(str2)\n",
    "        \n",
    "        dp = [[inf] * (N2+1) for _ in range(N1+1)] # 用来记录str1[:j]和str2[:j]能组成的最短序列\n",
    "        pre = [[None] * (N2+1) for _ in range(N1+1)] # 记录是从哪一个状态转移来的(可以倒推出上一个状态添加了那个字符形成了当前状态)\n",
    "        \n",
    "        for i in range(N1+1):\n",
    "            for j in range(N2+1):\n",
    "                if i == 0 or j == 0:\n",
    "                    dp[i][j] = i + j\n",
    "                    pre[i][j] = (max(0, i-1), max(0, j-1))\n",
    "        \n",
    "        for i in range(N1):\n",
    "            for j in range(N2):\n",
    "                if dp[i][j+1]+1 < dp[i+1][j+1]: # 如果在str1[:i-1]和str2[:j]形成的序列后面添加str1[i]更短\n",
    "                    dp[i+1][j+1] = dp[i][j+1]+1\n",
    "                    pre[i+1][j+1] = (i, j+1) # 记录上一个状态\n",
    "                if dp[i+1][j]+1 < dp[i+1][j+1]:\n",
    "                    dp[i+1][j+1] = dp[i+1][j]+1\n",
    "                    pre[i+1][j+1] = (i+1, j)\n",
    "                if str1[i] == str2[j] and dp[i][j] + 1 < dp[i+1][j+1]:\n",
    "                    dp[i+1][j+1] = dp[i][j] + 1\n",
    "                    pre[i+1][j+1] = (i, j)\n",
    "        \n",
    "        ans = []\n",
    "        cur = (N1, N2)\n",
    "        p = pre[-1][-1]\n",
    "        while cur != (0,0):\n",
    "            if cur[0] - p[0] == 1: # 如果第一维发生了变化, 说明添加的是str1中的字符\n",
    "                ans.append(str1[cur[0]-1])\n",
    "            else:\n",
    "                ans.append(str2[cur[1]-1])\n",
    "            \n",
    "            cur = p\n",
    "            p = pre[cur[0]][cur[1]]\n",
    "            \n",
    "            \n",
    "        \n",
    "        return \"\".join(ans[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        \n",
    "        '''\n",
    "        例如 abac 与 cab, 结果是cabac\n",
    "        对于结果中的任意字符, 只能属于str1一次, 但是也可以同时属于str1和str2\n",
    "        \n",
    "        '''\n",
    "        \n",
    "        N1 = len(str1)\n",
    "        N2 = len(str2)\n",
    "        \n",
    "        dp = [[inf] * (N2+1) for _ in range(N1+1)]\n",
    "        pre = [[None] * (N2+1) for _ in range(N1+1)]\n",
    "        \n",
    "        for i in range(N1+1):\n",
    "            for j in range(N2+1):\n",
    "                if i == 0 or j == 0:\n",
    "                    dp[i][j] = i + j\n",
    "                    pre[i][j] = (max(0, i-1), max(0, j-1))\n",
    "        \n",
    "        for i in range(N1):\n",
    "            for j in range(N2):\n",
    "                if dp[i][j+1]+1 < dp[i+1][j+1]:\n",
    "                    dp[i+1][j+1] = dp[i][j+1]+1\n",
    "                    pre[i+1][j+1] = (i, j+1)\n",
    "                if dp[i+1][j]+1 < dp[i+1][j+1]:\n",
    "                    dp[i+1][j+1] = dp[i+1][j]+1\n",
    "                    pre[i+1][j+1] = (i+1, j)\n",
    "                if str1[i] == str2[j] and dp[i][j] + 1 < dp[i+1][j+1]:\n",
    "                    dp[i+1][j+1] = dp[i][j] + 1\n",
    "                    pre[i+1][j+1] = (i, j)\n",
    "        \n",
    "        ans = []\n",
    "        cur = (N1, N2)\n",
    "        p = pre[-1][-1]\n",
    "        while cur != (0,0):\n",
    "            if cur[0] - p[0] == 1:\n",
    "                ans.append(str1[cur[0]-1])\n",
    "            else:\n",
    "                ans.append(str2[cur[1]-1])\n",
    "            \n",
    "            cur = p\n",
    "            p = pre[cur[0]][cur[1]]\n",
    "            \n",
    "            \n",
    "        \n",
    "        return \"\".join(ans[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(p1, p2):\n",
    "            if p1==len(str1): return str2[p2:]\n",
    "            if p2==len(str2): return str1[p1:]\n",
    "            if str1[p1] == str2[p2]: return str1[p1] + dfs(p1+1, p2+1)\n",
    "            a, b = str1[p1]+dfs(p1+1, p2), str2[p2]+dfs(p1, p2+1)\n",
    "            return a if len(a)<=len(b) else b\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(p1, p2):\n",
    "            if p1==len(str1) or p2==len(str2): return ''\n",
    "            if str1[p1] == str2[p2]: return str1[p1] + dfs(p1+1, p2+1)\n",
    "            a, b = dfs(p1+1, p2), dfs(p1, p2+1)\n",
    "            return a if len(a)>=len(b) else b\n",
    "        s = dfs(0, 0)\n",
    "        p1, p2, ps, res = 0, 0, 0, ''\n",
    "        while p1<=len(str1) and p2<=len(str2):\n",
    "            if ps==len(s): return res+str1[p1:]+str2[p2:]\n",
    "            if p1==len(str1): return res+str2[p2:]\n",
    "            if p2==len(str2): return res+str1[p1:]\n",
    "            if str1[p1] == str2[p2] == s[ps]:\n",
    "                res += s[ps]\n",
    "                p1 += 1\n",
    "                p2 += 1\n",
    "                ps += 1\n",
    "            elif str1[p1] == s[ps]:\n",
    "                res += str2[p2]\n",
    "                p2 += 1\n",
    "            else: \n",
    "                res += str1[p1]\n",
    "                p1 += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(p1, p2):\n",
    "            if p1==len(str1): return str2[p2:]\n",
    "            if p2==len(str2): return str1[p1:]\n",
    "            if str1[p1] == str2[p2]: return str1[p1] + dfs(p1+1, p2+1)\n",
    "            a, b = str1[p1]+dfs(p1+1, p2), str2[p2]+dfs(p1, p2+1)\n",
    "            return a if len(a)<=len(b) else b\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(p1, p2):\n",
    "            if p1==len(str1) or p2==len(str2): return ''\n",
    "            if str1[p1] == str2[p2]: return str1[p1] + dfs(p1+1, p2+1)\n",
    "            a, b = dfs(p1+1, p2), dfs(p1, p2+1)\n",
    "            return a if len(a)>=len(b) else b\n",
    "        p1, p2, ps, res, s = 0, 0, 0, '', dfs(0, 0)\n",
    "        while p1<=len(str1) and p2<=len(str2):\n",
    "            if ps==len(s): return res+str1[p1:]+str2[p2:]\n",
    "            if str1[p1] == str2[p2] == s[ps]:\n",
    "                res += s[ps]\n",
    "                p1 += 1\n",
    "                p2 += 1\n",
    "                ps += 1\n",
    "            elif str1[p1] == s[ps]:\n",
    "                res += str2[p2]\n",
    "                p2 += 1\n",
    "            else: \n",
    "                res += str1[p1]\n",
    "                p1 += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, s: str, t: str) -> str:\n",
    "        # 求以s,t两个字符串为子序列的最短字符串\n",
    "        \n",
    "        # 1. 递归\n",
    "        @cache\n",
    "        def dfs(i: int, j:int) -> int: # dfs(i,j)返回s的前i个字母和t的前i个字母的最短公共超序列长度\n",
    "            if i < 0: return j + 1 \n",
    "            if j < 0: return i + 1\n",
    "            if s[i] == t[j]:\n",
    "                return dfs(i - 1, j - 1) + 1\n",
    "            return min(dfs(i - 1, j), dfs(i, j - 1)) + 1\n",
    "\n",
    "        def make_ans(i:int, j:int) -> str: # make_ans(i,j) 返回 s 的前 i 个字母和 t 的前 j 个字母的最短公共超序列\n",
    "            if i < 0: return t[:j + 1]\n",
    "            if j < 0: return s[:i + 1]\n",
    "            if s[i] == t[j]:\n",
    "                return make_ans(i - 1, j - 1) + s[i]\n",
    "            if dfs(i, j) == dfs(i - 1, j) + 1:\n",
    "                return make_ans(i - 1, j) + s[i]\n",
    "            return make_ans(i, j - 1) + t[j]\n",
    "        return make_ans(len(s) - 1, len(t) - 1)\n",
    "\n",
    "        # 2. 迭代\n",
    "        # n, m = len(s), len(t)\n",
    "        # f = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        # f[0] = list(range(m + 1))\n",
    "        # for i in range(1, n + 1):\n",
    "        #     f[i][0] = i\n",
    "        # for i,x in enumerate(s):\n",
    "        #     for j, y in enumerate(t):\n",
    "        #         if x == y:\n",
    "        #             f[i + 1][j + 1] = f[i][j] + 1\n",
    "        #         else:\n",
    "        #             f[i + 1][j + 1] = min(f[i][j + 1], f[i + 1][j]) + 1\n",
    "        # ans = []\n",
    "        # i, j = n - 1, m - 1\n",
    "        # while i >= 0 and j >= 0:\n",
    "        #     if s[i] == t[j]:\n",
    "        #         ans.append(s[i])\n",
    "        #         i -= 1\n",
    "        #         j -= 1\n",
    "        #     elif f[i + 1][j + 1] == f[i][j + 1] + 1:\n",
    "        #         ans.append(s[i])\n",
    "        #         i -= 1\n",
    "        #     else:\n",
    "        #         ans.append(t[j])\n",
    "        #         j -= 1\n",
    "        # return s[:i + 1] + t[:j + 1] + ''.join(reversed(ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, s: str, t: str) -> str:\n",
    "        # 一个dfs会超内存\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0:\n",
    "        #         return t[:j+1]\n",
    "        #     if j < 0:\n",
    "        #         return s[:i+1]\n",
    "        #     if s[i] == t[j]:\n",
    "        #         return dfs(i-1, j-1) + s[i]\n",
    "        #     ans1 = dfs(i-1, j)\n",
    "        #     ans2 = dfs(i, j-1)\n",
    "        #     if len(ans1) < len(ans2):\n",
    "        #         return ans1 + s[i]\n",
    "        #     return ans2 + t[j]\n",
    "        # return dfs(len(s)-1, len(t)-1)\n",
    "\n",
    "\n",
    "        # 换根DP\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0:\n",
    "                return j + 1\n",
    "            if j < 0:\n",
    "                return i + 1\n",
    "            if s[i] == t[j]:\n",
    "                return dfs(i-1, j-1) + 1\n",
    "            return min(dfs(i-1, j), dfs(i, j-1)) + 1\n",
    "        \n",
    "        # make_ans(i, j) 返回s的前i个字母和t的前j个字母的最短公共超序列\n",
    "        # 与dfs的区别在于末尾的递归时if-else\n",
    "        # make_ans(i-1, j)和make_ans(i, j-1)都不会调用\n",
    "        # 所以make_ans的递归树只是一条链\n",
    "        def make_ans(i, j):\n",
    "            if i < 0:\n",
    "                return t[:j+1]\n",
    "            if j < 0:\n",
    "                return s[:i+1]\n",
    "            if s[i] == t[j]:\n",
    "                return make_ans(i-1, j-1) + s[i]\n",
    "            # 如果下面 if 成立，说明上面 dfs 中的 min 取的是 dfs(i - 1, j)\n",
    "            # 说明 dfs(i - 1, j) 对应的公共超序列更短\n",
    "            # 那么就在 make_ans(i - 1, j) 的结果后面加上 s[i]\n",
    "            # 否则说明 dfs(i, j - 1) 对应的公共超序列更短\n",
    "            # 那么就在 make_ans(i, j - 1) 的结果后面加上 t[j]\n",
    "            if dfs(i, j) == dfs(i-1, j) + 1:\n",
    "                return make_ans(i-1, j) + s[i]\n",
    "            return make_ans(i, j-1) + t[j]\n",
    "\n",
    "        return make_ans(len(s) -1, len(t) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, s: str, t: str) -> str:\n",
    "        # 求以s,t两个字符串为子序列的最短字符串\n",
    "        \n",
    "        # 1. 递归\n",
    "        @cache\n",
    "        def dfs(i: int, j:int) -> int:\n",
    "            if i < 0: return j + 1 \n",
    "            if j < 0: return i + 1\n",
    "            if s[i] == t[j]:\n",
    "                return dfs(i - 1, j - 1) + 1\n",
    "            return min(dfs(i - 1, j), dfs(i, j - 1)) + 1\n",
    "        def make_ans(i:int, j:int) -> str:\n",
    "            if i < 0: return t[:j + 1]\n",
    "            if j < 0: return s[:i + 1]\n",
    "            if s[i] == t[j]:\n",
    "                return make_ans(i - 1, j - 1) + s[i]\n",
    "            if dfs(i, j) == dfs(i - 1, j) + 1:\n",
    "                return make_ans(i - 1, j) + s[i]\n",
    "            return make_ans(i, j - 1) + t[j]\n",
    "        return make_ans(len(s) - 1, len(t) - 1)\n",
    "\n",
    "        # 2. 迭代\n",
    "        # n, m = len(s), len(t)\n",
    "        # f = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        # f[0] = list(range(m + 1))\n",
    "        # for i in range(1, n + 1):\n",
    "        #     f[i][0] = i\n",
    "        # for i,x in enumerate(s):\n",
    "        #     for j, y in enumerate(t):\n",
    "        #         if x == y:\n",
    "        #             f[i + 1][j + 1] = f[i][j] + 1\n",
    "        #         else:\n",
    "        #             f[i + 1][j + 1] = min(f[i][j + 1], f[i + 1][j]) + 1\n",
    "        # ans = []\n",
    "        # i, j = n - 1, m - 1\n",
    "        # while i >= 0 and j >= 0:\n",
    "        #     if s[i] == t[j]:\n",
    "        #         ans.append(s[i])\n",
    "        #         i -= 1\n",
    "        #         j -= 1\n",
    "        #     elif f[i + 1][j + 1] == f[i][j + 1] + 1:\n",
    "        #         ans.append(s[i])\n",
    "        #         i -= 1\n",
    "        #     else:\n",
    "        #         ans.append(t[j])\n",
    "        #         j -= 1\n",
    "        # return s[:i + 1] + t[:j + 1] + ''.join(reversed(ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, s: str, t: str) -> str:\n",
    "        # dfs(i,j) 返回 s 的前 i 个字母和 t 的前 j 个字母的最短公共超序列的长度\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0: return j + 1  # s 是空串，返回剩余的 t 的长度\n",
    "            if j < 0: return i + 1  # t 是空串，返回剩余的 s 的长度\n",
    "            if s[i] == t[j]:  # 最短公共超序列一定包含 s[i]\n",
    "                return dfs(i - 1, j - 1) + 1\n",
    "            return min(dfs(i - 1, j), dfs(i, j - 1)) + 1\n",
    "\n",
    "        # make_ans(i,j) 返回 s 的前 i 个字母和 t 的前 j 个字母的最短公共超序列\n",
    "        # 看上去和 dfs 没啥区别，但是末尾的递归是 if-else\n",
    "        # make_ans(i-1,j) 和 make_ans(i,j-1) 不会都调用\n",
    "        # 所以 make_ans 的递归树仅仅是一条链\n",
    "        def make_ans(i: int, j: int) -> str:\n",
    "            if i < 0: return t[:j + 1]  # s 是空串，返回剩余的 t\n",
    "            if j < 0: return s[:i + 1]  # t 是空串，返回剩余的 s\n",
    "            if s[i] == t[j]:  # 公共超序列一定包含 s[i]\n",
    "                return make_ans(i - 1, j - 1) + s[i]\n",
    "            # 如果下面 if 成立，说明上面 dfs 中的 min 取的是 dfs(i - 1, j)\n",
    "            # 说明 dfs(i - 1, j) 对应的公共超序列更短\n",
    "            # 那么就在 make_ans(i - 1, j) 的结果后面加上 s[i]\n",
    "            # 否则说明 dfs(i, j - 1) 对应的公共超序列更短\n",
    "            # 那么就在 make_ans(i, j - 1) 的结果后面加上 t[j]\n",
    "            if dfs(i, j) == dfs(i - 1, j) + 1:\n",
    "                return make_ans(i - 1, j) + s[i]\n",
    "            return make_ans(i, j - 1) + t[j]\n",
    "\n",
    "        return make_ans(len(s) - 1, len(t) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, s: str, t: str) -> str:\n",
    "        # dfs(i, j)返回s的前i个字母好t的前j个字母的最短公共超序列长度\n",
    "        @cache\n",
    "        def dfs(i:int, j:int) ->int:\n",
    "            if i <0: return j+1 #s是空串，返回剩余t的长度\n",
    "            if j <0: return i+1 #t是空串，返回剩余s的长度\n",
    "            if s[i] == t[j]: # 最短公共超序序列一定包含s[i]\n",
    "                return dfs(i - 1, j - 1)+1\n",
    "            return min(dfs(i - 1, j), dfs(i, j - 1))+1\n",
    "\n",
    "        def make_ans(i:int, j:int) ->str:\n",
    "            if i <0: return t[:j +1] # s是空串，返回剩余的t\n",
    "            if j < 0: return s[:i +1] #t 是空串，返回剩余的s\n",
    "            if s[i] == t[j]: # 公共超序列一定包含s[i]\n",
    "                return make_ans(i - 1, j - 1)  +s[i]\n",
    "            if dfs(i, j) == dfs(i -1 ,j) +1:\n",
    "                return make_ans(i - 1, j) +s[i]\n",
    "            return make_ans(i, j - 1) +t[j]\n",
    "        return make_ans(len(s) - 1, len(t) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i < 0: return j + 1\n",
    "            if j < 0: return i + 1\n",
    "            if str1[i] == str2[j]:\n",
    "                return dfs(i - 1,j - 1) + 1\n",
    "            ans1 = dfs(i - 1,j)\n",
    "            ans2 = dfs(i,j - 1)\n",
    "            if ans1 < ans2:\n",
    "                return ans1 + 1\n",
    "            return ans2 + 1\n",
    "        def solve(i,j):\n",
    "            if i < 0: return str2[:j + 1]\n",
    "            if j < 0: return str1[:i + 1]\n",
    "            if str1[i] == str2[j]:\n",
    "                return solve(i - 1,j - 1) + str1[i]\n",
    "            if dfs(i - 1,j) < dfs(i,j - 1):\n",
    "                return solve(i - 1,j) + str1[i]\n",
    "            return solve(i,j - 1) + str2[j]\n",
    "        return solve(len(str1) - 1,len(str2) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, s: str, t: str) -> str:\n",
    "        # 核心思想：从后往前选+优化\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            # s和t的公共最短字符串\n",
    "            if i < 0:return j+1\n",
    "            if j < 0:return i+1\n",
    "            if s[i] == t[j]:\n",
    "                return dfs(i-1,j-1) + 1\n",
    "            return min(dfs(i-1,j),dfs(i,j-1))+1\n",
    "\n",
    "        \n",
    "        def make_ans(i,j):\n",
    "            # s和t的公共最短字符串\n",
    "            if i < 0:return t[:j+1]\n",
    "            if j < 0:return s[:i+1]\n",
    "            if s[i] == t[j]:\n",
    "                return make_ans(i-1,j-1) + s[i]\n",
    "            if dfs(i-1,j)+1 == dfs(i,j):\n",
    "                return make_ans(i-1,j) + s[i]\n",
    "            return make_ans(i,j-1) + t[j]\n",
    "        return make_ans(len(s)-1,len(t)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, s: str, t: str) -> str:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i < 0:return j + 1\n",
    "            if j < 0:return i + 1\n",
    "            if s[i] == t[j]:\n",
    "                return dfs(i-1,j-1) + 1\n",
    "            return min(dfs(i,j-1),dfs(i-1,j)) + 1\n",
    "\n",
    "\n",
    "        def make_ans(i,j):\n",
    "            if i < 0:return t[:j+1]\n",
    "            if j < 0:return s[:i+1]\n",
    "            if s[i] == t[j]:\n",
    "                return make_ans(i-1,j-1)+s[i]\n",
    "            if dfs(i, j) == dfs(i - 1, j) + 1:\n",
    "                return make_ans(i-1,j) + s[i]\n",
    "            return make_ans(i,j-1) + t[j]\n",
    "\n",
    "        return make_ans(len(s)-1,len(t)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestCommonSupersequence(self, a: str, b: str) -> str:\n",
    "        # 两个字符串的最长公共子序列\n",
    "        n = len(a)\n",
    "        m = len(b)\n",
    "        @cache \n",
    "        def dfs(i,j):\n",
    "            if i<0 or j<0:\n",
    "                return i+1 if j<0 else j+1\n",
    "            if a[i]==b[j]:\n",
    "                return dfs(i-1,j-1)+1\n",
    "            s1 = dfs(i-1,j)\n",
    "            s2 = dfs(i,j-1)\n",
    "            return min(s1,s2)+1\n",
    "        @cache\n",
    "        def make_ans(i,j):\n",
    "            if i<0 or j<0:\n",
    "                return b[:j+1] if i<0 else a[:i+1]\n",
    "            if a[i]==b[j]:\n",
    "                return make_ans(i-1,j-1)+a[i]\n",
    "            if dfs(i,j)==dfs(i-1,j)+1:\n",
    "                return make_ans(i-1,j)+a[i]\n",
    "            return make_ans(i,j-1)+b[j]\n",
    "        ans = make_ans(n-1,m-1)\n",
    "        return  ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
